﻿#include<iostream>
using namespace std;
#include<vector>

#include <algorithm>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param V int整型
     * @param num int整型vector
     * @return int整型
     */
    //aaaaaaaaaaa
    sixnisnx
        ijijoijiji
    int arr[30][20000] = { 0 };
    int boxin(int V, vector<int>& num) {
        // write code here
        for (size_t i = 0; i < num.size(); i++)
        {
            arr[i][0] = 0;
        }
        for (size_t i = 0; i <= V; i++)
        {
            arr[0][V] = 0;
        }
        for (size_t i = 1; i <= num.size(); i++)
        {
            for (size_t j = 1; j <= V; j++) {
                if (j - num[i] > 0)
                {
                    arr[i - 1][j] = max(arr[i - 2][j], arr[i - 2][j - num[i - 1]] + num[i - 1]);
                }
                else {
                    arr[i - 1][j] = arr[i - 2][j];
                }
            }
        }
        return V - arr[num.size() - 1][V];
    }
};
int main()
{
    Solution solution;
    vector<int> vi = { 8,3,12,7,9,7 };
    cout << solution.boxin(24, vi);
    return 0;
}